#include <stdio.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
typedef char ElemType;
typedef struct treeNode {
  ElemType data;
  struct treeNode *parent;
  struct treeNode *lchild,  *rchild;
} TNODE;
typedef struct btree {
  TNODE *root;
  struct btree *left,  *right;
} BTREE;
void InitBtree(BTREE *tree, TNODE *node) {
  tree->root = node;
  tree->left = tree->right = NULL;
}
void DispMiddle(BTREE *tree) {
  if (tree->left != NULL) {
    DispMiddle(tree->left);
  }
  printf("%c ", tree->root->data);
  if (tree->right != NULL) {
    DispMiddle(tree->right);
  }
}
void Clear(TNODE *node, char c) {
  node->data = c;
  node->lchild = node->rchild = node->parent = NULL;
}
void PutLeft(TNODE *node, BTREE *tree) {
  node->lchild = tree->root;
  tree->root->parent = node;
}
void PutRight(TNODE *node, BTREE *tree) {
  node->rchild = tree->root;
  tree->root->parent = node;
}
int size(BTREE *bt) {
  if (bt->left == NULL && bt->right == NULL)
    return 1;
  if (bt->left == NULL)
    return 1+size(bt->right);
  if (bt->right == NULL)
    return 1+size(bt->left);
  return size(bt->left) + size(bt->right) + 1;
}
int depth(BTREE *bt) {
  if (bt->left == NULL && bt->right == NULL)
    return 0;
  if (bt->left == NULL)
    return 1+depth(bt->right);
  if (bt->right == NULL)
    return 1+depth(bt->left);
  return MAX(depth(bt->left), depth(bt->right)) + 1;
}
int main() {
  TNODE a, b, c;
  Clear(&a, 'A');
  Clear(&b, 'B');
  Clear(&c, 'C');
  BTREE ta, tb, tc;
  InitBtree(&ta, &a);
  InitBtree(&tb, &b);
  InitBtree(&tc, &c);
  DispMiddle(&ta);
  putchar('\n');
  printf("size(ta)=%d\n", size(&ta));
  printf("depth(ta)=%d\n", depth(&ta));
  ta.left = &tb;
  DispMiddle(&ta);
  putchar('\n');
  printf("size(ta)=%d\n", size(&ta));
  printf("depth(ta)=%d\n", depth(&ta));
  tb.right = &tc;
  DispMiddle(&ta);
  putchar('\n');
  printf("size(ta)=%d\n", size(&ta));
  printf("depth(ta)=%d\n", depth(&ta));
  return 0;
}
